package com.tanzc.sort;

import com.tanzc.util.ArrayUtils;

import java.util.Date;

/**
 * <p> description: 冒泡排序</p>
 *
 * @author tanzc
 * @date 2021/12/23
 **/
public class BubbleSort {
    public static void main(String[] args) {
        BubbleSort bubbleSort = new BubbleSort();
        int num = 100000, max = 100000;
        int[] arr = ArrayUtils.random(num, max);
//        int[] arr = bubbleSort.worst(num);
//        int[] arr = bubbleSort.bad(num);
//        int[] arr = bubbleSort.nice(num);
        int[] arr1 = new int[num];
        int[] arr2 = new int[num];
        int[] arr3 = new int[num];
        System.arraycopy(arr, 0, arr1, 0, num);
        System.arraycopy(arr, 0, arr2, 0, num);
        System.arraycopy(arr, 0, arr3, 0, num);

        System.out.print("原始版本的冒泡-----time: ");
        Date start = new Date();
        bubbleSort.bubble(arr1);
        Date end = new Date();
        long timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        bubbleSort.printArray(arr1);

        System.out.print("削去无效轮数的冒泡-----针对中途排好序的序列-----time: ");
        start = new Date();
        bubbleSort.bubble2(arr2);
        end = new Date();
        timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        bubbleSort.printArray(arr2);

        System.out.print("缩减有序区的冒泡-----针对存在已有序的序列-----time: ");
        start = new Date();
        bubbleSort.bubble3(arr3);
        end = new Date();
        timediff = end.getTime() - start.getTime();
        System.out.println(timediff + "ms");
//        bubbleSort.printArray(arr3);

    }


    /**
     * 冒泡排序应该是最简单无脑的排序了
     * 每次比较相邻位置两元素的大小, 根据排序规则调整位置
     * 一轮比较可以把最大/最小的元素找到并移到最大/最小位置, 比较次数应是该轮元素数 n - 1
     * 下一轮比较则可以不管最大/最小元素了, 少比较一个数, 比较轮数应是总元素数 n - 1
     * <p>
     * 时间复杂度: 外层循环n - 1次，内层循环n - i - 1次，O(n²)
     *
     * @param arr
     * @return
     */
    public int[] bubble(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
        return arr;
    }

    /**
     * 冒泡排序优化版
     * 在每轮排序中，使用一个布尔值记录本轮是否有元素交换，若本轮没有元素交换，说明元素已经有序，此时可以直接退出外循环
     * <p>
     * 此版改进，避免了在列表已经有序的情况下，再进行无效的比较
     *
     * @param arr
     * @return
     */
    public int[] bubble2(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean sorted = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    sorted = false;
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            if (sorted) {
                break;
            }
        }
        return arr;
    }

    /**
     * 冒泡配许优化版本
     * 在每轮冒泡中，记录发生元素交换的位置
     * 根据冒泡的原理，每轮冒泡的最后一次交换位置后面的元素都是有序的
     * 可能出现某次冒泡中，只冒泡到了中间，因为可能有些元素比冒泡的元素大且已有序了
     * 所以下轮冒泡，不需要再冒泡到这些区域，也就是减少了单轮冒泡的范围
     *
     * @param arr
     */
    public void bubble3(int[] arr) {
        int tmp;
        int lastExchange = 0;
        int sortEnder = arr.length - 1;
        for (int i = 0; i < arr.length - 1; i++) {
            boolean sorted = true;
            for (int j = 0; j < sortEnder; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    sorted = false;
                    lastExchange = j;
                }
            }
            sortEnder = lastExchange;
            if (sorted) {
                break;
            }
        }
    }

    /**
     * 生成随机数
     *
     * @param num
     * @param max
     * @return
     */
    public int[] random(int num, int max) {
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            int x = (int) (Math.random() * (max + 1));
            arr[i] = x;
        }
        System.out.println("待排序数据形式: 5 6 11 7 13 9 14 2 15 8");
        System.out.println("待排序数据:");
        printArray(arr);
        return arr;
    }

    /**
     * 最好情况
     * @param num
     * @return
     */
    public int[] nice(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = i;
        }
        System.out.println("待排序数据形式: 1 2 3 4 5 6 7 8 9 10");
        System.out.println("待排序数据:");
        printArray(arr);
        return arr;
    }

    /**
     * 最坏情况
     * @param num
     * @return
     */
    public int[] worst(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < num; i++) {
            arr[i] = num - i;
        }
        System.out.println("待排序数据形式: 10 9 8 7 6 5 4 3 2 1");
        System.out.println("待排序数据:");
        printArray(arr);
        return arr;
    }

    /**
     * 一半最好，一半最坏
     * @param num
     * @return
     */
    public int[] bad(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < num / 2; i++) {
            arr[i] = num / 2 - i;
        }
        for (int i = num / 2; i < num; i++) {
            arr[i] = i;
        }
        System.out.println("待排序数据形式: 5 4 3 2 1 6 7 8 9 10");
        System.out.println("待排序数据:");
        printArray(arr);
        return arr;
    }

    public void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d ", arr[i]);
        }
        System.out.println();
    }
}
